package offer.secnod;

import binaryTree.basic.TreeNode;

import java.util.HashMap;

public class Offer07 {
    HashMap<Integer, Integer> map = new HashMap<>();
//    public TreeNode rebuild(int[] preOrder,int[] inOrder){
//        for (int i = 0; i < inOrder.length; i++) {
//            map.put(inOrder[i],i );
//        }
//
//
//
//    }

    public TreeNode builds(int[] preOrder,int preStart,int preEnd,int[] inOrder,int inStart,int inEnd){
       if (preStart>preEnd) {
           return null;
       }
        TreeNode root = new TreeNode(preOrder[preStart]);

        Integer index = map.get(preOrder[preStart]);
        int leftNodes=index-inStart;

        root.left=builds(preOrder,preStart+1,preStart+leftNodes,inOrder,inStart,index-1);
        root.right=builds(preOrder,preStart+leftNodes+1,preEnd,inOrder,index+1,inEnd);
        return root;

    }



    HashMap<Integer, Integer> valtoIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valtoIndex.put(inorder[i], i);
        }

        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    //TODO:2023/8/17   单拿出一个方法来想怎么递归  不要在给出的代码上想怎么递归
    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {

        if (preStart>preEnd){
            return null;
        }

        int rootVal=preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        Integer index = valtoIndex.get(rootVal);
        int leftNodeNums=index-inStart;
        root.left=build(preorder,preStart+1,preStart+leftNodeNums,inorder,inStart,index-1);
        root.right=build(preorder,preStart+leftNodeNums+1,preEnd,inorder,index+1,inEnd);

        return root;
    }

}
